public class Solution {

    /*
      动态规划解法：

        g[i] 表示以i位置为结尾的所有子数组的最小和
        环形数组的子数组的最大和有两种情况：
        1.拥有最大和的子数组就在数组的中间
        2.环形数组的头部和尾部共同组成了拥有最大和的子数组
        我们只需要求两种情况的最大值，再确定哪种更大返回即可

        对于1：
         f[i] 表示以i位置为结尾的所有子数组的最大和
         当长度为1时，子数组的最大和为nums[i]
         当长度大于1时，子数组的最大和nums[i]+f[i-1]
        状态转移方程： f[i]=Math.max(nums[i],f[i-1]);

        对于2：
        转化为求数组中间的最小子数组和，用数组总和sum-数组中间的最小子数组和(gmin)
        同理:
        最小和的状态转移方程： g[i]=Math.min(nums[i],g[i-1]);

        初始化：可以添加一个虚拟的头部，在状态数组里多开一个空间，填入0
         可以使填了0可以使原来的结果不变，f[0]=g[0]=0,
         循环填状态方程时就可以直接从1开始，状态数组多加了一个格子，注意下标映射
         原数组nums[i]变成nums[i-1]

         返回值：注意如果数组全部为负数如 [-1,-2,-3],
         那么最大的子数组应该在数组中间，直接返回fmax

     */   public int maxSubarraySumCircular(int[] nums) {

        int n=nums.length;

        int[] f=new int[n+1];
        int[] g=new int[n+1];
        int fmax=Integer.MIN_VALUE;
        int gmin=Integer.MAX_VALUE;
        int sum=0;

        for(int i=1;i<=n;i++){

            sum+=nums[i-1]; //求总数组和
            f[i] = Math.max(nums[i-1],nums[i-1] + f[i-1]);
            fmax = Math.max(fmax,f[i]);//求数组中间的最大子数组和

            g[i] = Math.min(nums[i-1],nums[i-1] + g[i-1]);
            gmin = Math.min(gmin,g[i]);//求数组中间的最小子数组和

        }
        //判断数组是否全为负数，如果是直接返回fmax,不是判断1，2情况哪个大
        return  sum==gmin ? fmax:Math.max(fmax,sum-gmin);

    }
}